1. Field of the Invention
The present invention relates to the field of computer systems architecture. More particularly, the invention relates to system bus arbitration protocols.
2. Description of the Related Art
In the design of an efficient system architecture with a number of subsystems, e.g., a multi-processor system, the use of a common system bus shared by the sub-systems is useful for satisfying several important design goals. These goals include minimizing the total number and cost of interconnections between the sub-systems, maintaining modularity in the interfaces of sub-systems, and simplifying the integration of interfaces for add-on sub-systems, e.g., expanded memory and peripherals. However, sharing a system bus necessitates the use of a bus arbitration protocol to resolve the inevitable bus contentions from the sub-systems.
Conventional bus arbitration protocols for resolving bus contentions can be divided into two general classes; centralized arbitration and distributed arbitration protocols. In an exemplary conventional centralized arbitration system 110, as shown in FIG. 1A, system 110 includes processors 111, 112, 113, 114, a system bus 118 and a centralized arbiter 119. System bus 118, e.g., Address.sub.-- bus, is coupled to processors 111, 112, 113, 114 and centralized arbiter 119. In addition, each of processors 111, 112, 113,114 is coupled to centralized arbiter 119 by one of bus request lines Req.sub.-- 0, Req.sub.-- 1, Req.sub.-- 2, Req.sub.-- 3, and one of bus grant lines Bus.sub.-- Grant.sub.-- 0, Bus.sub.-- Grant.sub.-- 1, Bus.sub.-- Grant.sub.-- 2, Bus.sub.-- Grant.sub.-- 3, respectively.
Centralized arbiter 119 is the sole bus arbiter and is responsible for arbitrating all bus contentions. When one of processors 111, 112, 113, 114 needs to drive system bus 118, a request is made to centralized arbiter 119 via the appropriate bus request line. If no other processor is contending for system bus 118, centralized arbiter 119 assigns bus 118 to the requesting processor. Conversely, if two or more processors make a bus request within a pre-determined period, centralized arbiter 119 uses a suitable allocation scheme, e.g., a round robin or a predetermined priority scheme, to decide what processor should be assigned the next bus master. In either case, centralized arbiter 119 communicates the bus grant to the assigned processor via the appropriate bus grant line. For example, processor 111 makes a request to arbiter 119 via bus request line Req.sub.-- 0 and eventually receives a grant from arbiter 119 via bus grant line Bus.sub.-- Grant.sub.-- 0.
FIG. 1B is a block diagram of a conventional distributed arbitration system 120 which includes processors 121, 122, 123, 124 and a system bus 128. System bus 128, e.g., Address.sub.-- bus, is coupled to processors 121, 122, 123, 124. In addition, processors 121, 122, 123, 124 are coupled to each other by bus request lines Req.sub.-- 0, Req.sub.-- 1, Req.sub.-- 2, Req.sub.-- 3 and also by bus control lines Bus.sub.-- Busy.sub.-- 0, Bus.sub.-- Busy.sub.-- 1, Bus.sub.-- Busy.sub.-- 2, Bus.sub.-- Busy.sub.-- 3.
The distributed arbitration protocol dictates that all processors 121, 122, 123, 124 are responsible for simultaneously arbitrating bus contentions and assigning the same processor to be the next bus master. For example, when one of processors 121, 122, 123, 124 needs to drive system bus 128, a request is broadcasted to every other processor coupled to bus 128 via the appropriate bus request line. If no other processor is contending for system bus 128, all the other processors will independently assign bus 118 to the requesting processor. Conversely, if two or more processors make a bus request within a pre-determined period, then each of processors 121, 122, 123, 124 uses a suitable identical allocation scheme to independently arrive at the same conclusion as to which processor should be the next bus master. In either case, the processor assigned to be the next bus master captures system bus 128 by asserting the appropriate bus busy line, thereby communicating to all the other processors that system bus 128 is now in use. For example, processor 121 broadcasts a bus request on bus request line Req.sub.-- 0. When system bus 128 is free and none of the other bus request lines Req.sub.-- 1, Req.sub.-- 2 and Req.sub.-- 3 has been asserted by a processor with higher priority, processor 121 proceeds to capture system bus 128 by asserting bus control line Bus.sub.-- Busy.sub.-- 0. Appendix A is a specification of one such distributed arbitration scheme, named the "Futurebus+" based on the I.E.E.E.Standard 896.2-1991.
In most conventional bus arbitration protocols, such as the above mentioned protocols, in order to minimize the overall delay arising from bus arbitration, the sequential tasks of sending and receiving a bus request, and assigning the next bus master are completed in the same system clock cycle. While it is expedient to attempt to complete processing of the bus request and the corresponding bus driver assignment in one system clock cycle, as the system clock speed increases in response to processors with faster processor clocks, the ability to receive a bus request and complete the arbitration process within a single fast system clock cycle is no longer attainable. Hence, these conventional bus arbitration protocols are not scalable with respect to faster processors. A system designer is forced to either slow the system clock speed or to use multiple system clock cycles for resolving bus contentions. As a result, the performance is inhibited by either a slower system clock speed or extra system clock latencies inserted for solely arbitrating bus contentions.
Hence, there is a need for a solution to the bus arbitration problem that is efficient, cost effective, modular and scalable as processor clock speeds increase.